Skip to main content

Full text of "BSTJ 50: 1. January 1971: On Benes Rearrangeable Networks. (Hwang, F.K.)"

See other formats


On Benes Rearrangeable Networks 

By F. K. HWANG 

(Manuscript received July 31, 1970) 

V. E. Benel considered a class of multi-stage switching networks 1 and 
proved that if the linkage pattern between two stages is chosen in a specific 
way, then the resulting networks are rearrangeable. We offer a simpler 
proof by pointing out the relation between Benel class networks and the 
Slepian-Duguid Theorem on three-stage Clos networks. 

I. INTRODUCTION 

V. E. Benes 1 considered the class, denoted here by /*(%, n?, . . . 
nt + i), of all connecting networks v with the following properties: 

(i) v is two sided, with N terminals on each side where N = H \1\ n % . 
(ii) v is built of an odd number s = 2t + 1 of stages f* , 
k = 1, • • • 2t + 1 connected as specified by permutations 
<pi , • • • <p2« • In the notation of BeneS, 

" — fi^ifa * " ' Vaifai + i • 

(Hi) f k consists of N/n k identical square switches of size n k . 
(iv) ft = f 2 < + 2-t for k = 1, • ■ • t. 

Bene§ proceeded to prescribe a specific way of choosing <p k (See 
page 113 of Ref 1): 

"Order the switches of each stage; to define <p k for a given 1 S k ^ t, 
take the first switch of f* , say with n k outlet and n k a divisor of N, 
and connect these outlets one to each of the first n k switch of f*+i ; 
go on to the second switch of f * and connect its n k outlets one to each 
of the next n k switches of f A+ i ; when all the switches of f*+i have one 
link on the inlet side, start again with the first switch; proceed cyclically 
in this way till all the outlets of f t are assigned." 

BeneS also specified <p k = <p 3 , + 1 _ t for A; = t + 1, • • • 2t. We call a 
network v c B(n t , n 2 , • ■ • n f + 1 ) constructed in this manner a cyclic 
Bene§ network. 

201 



202 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971 

Benes proved that a cyclic Benes network is rearrangeable. The 
proof given by Benes in Ref. 1 is, however, quite lengthy and involved. 
In the present work, we offer an alternate proof by pointing out the 
links between cyclic Benes networks and the Slepian-Duguid Theorem 
on three-stage Clos networks. It is hoped that the simpler proof will 
lead to new insights into the problem of constructing rearrangeable 
networks. 

II. MULTISTAGE REARRANGEABLE NETWORKS 

We show a way to construct v e B(rii , n 2 , ■ • • n l + l ) from v' t 
B(n 2 ,n 3 , • • • ?i, +0 such that if v' is rearrangeable then v is rearrangeable. 

We construct a three-stage network by having the first stage and 
the third stage each consist of N/n* copies of n x X n x square switches, 
A x ■ • • A N/ni , Ci ■ ■ • C N/ni say, where the second stage consists of 
n x copies of v' ', say, B x , ■ ■ ■ B ni . Each switch in the first stage and the 
third stage is then linked to every 5, in the second stage. (It does not 
matter which inlet or outlet of 5, is finked to which A, or which C,- .) 
This gives a network v e B(?ii , n 2 , • • • n l+1 ). Now if v' is also con- 
structed in this manner and so on down to the three-stage network, 
we then call v a Bene§ network. That a Bene§ network is rearrangeable 
will follow from a multistage version of the Slepian-Duguid Theorem 
on three-stage Clos networks. To be complete, we state this multistage 
version and give a proof. 

Theorem. 1: Let v e B{n x , n 2 , • • • n, + I ) be a Benes network. Then v is 
rearrangeable. 

Proof: For t = 0, we have a special case of awi X n x square switch 
which is clearly rearrangeable and no construction is needed. Supposing 
that Theorem 1 is true for t' = t — 1 ^ 0, we prove Theorem 1 for 

t' = t. 

A maximal assignment between each inlet terminal and each outlet 
terminal is a permutation tp of the set of numbers [i : i = 1,2, • • • N} 
where iV = XI /-J n > ■ (Following Bene§, we need only consider maximal 
assignments.) A given maximal assignment can also be viewed as a 
set of defining relationships between each switch in the first stage and 
each switch in the third stage (treating the set of v' as the second 
stage). Set N 2 = n 2 • n 3 • • • ■ n t+1 , note that N = thNt . Let A, be 
the ith. switch in the first stage, A = [ A { : % = 1, 2, • • • N a ] and C f 
be the jth. switch in the third stage, C = {C,- : j = 1, 2, • • • N 2 }. Con- 
sider a particular first stage switch A, . Suppose the n x inlet terminals of 



REARRANGEABLE NETWORKS 



203 



A { are assigned by <p to third-stage outlet terminals, y lX , y i2 , ■ ■ • y<» • 
Denote by Y ih (Y ik t C) the third-stage switch that contains y ik , k = 
1, 2, -Jh, and let S t = { Y ik : k = 1, 2, • • • n x } . Since U?-i & has 
a total of aj-ni elements and since each distinct element has only n x 
repetitions, there are at least x distinct elements in {JUi 8 t for each 
x = 1,2, ••■ N 2 . Hence the condition of P. Hall's Theorem 2 on distinct 
representation of subsets is satisfied and there exists a set Z = \Z t :i = 
1, 2, • • • N 2 } such that Z, e S t and Z = C. Then &< , i = 1, • • • N 2 
can be chosen such that x t e A,- , <px { e Z, . Now we may choose to route 
the rii calls x { -» pre,- through the first second-stage switch Bj , which 
by induction hypothesis is rearrangeable. The problem is then reduced 
to that of a maximal assignment in a network of type B{n x — 1, n 2 , ••■ 
n l+ i). By repeatedly applying the same argument, we obtain sub- 
assignments on each B k . 

III. CYCLIC BENES NETWORKS 

Theorem 2: Every cyclic Benel network is a Benes network, hence is 
rearrangeable. 

Proof: A single stage cyclic Benes network is a N X N square matrix, 
which is a Benes network. Suppose Theorem 2 is true for (2t — 1) 
stage network where t ^ 1. We prove a (2t + 1) stage cyclic Bene§ 
network is a Bene§ network. 

Let v = S^U ■ • • Pxfii+i £ Bin! , n 2 , • • • n t+1 ) be a cyclic Benes 
network. We shall show that the complex p = £ 2 (p 2 {a ■ ■ ' <p 2 t-i^2i 
can be decomposed into n x copies of v where v' t B(n 2 , n 3 • • • n t+1 ) 
is also a cyclic Beneg network. Furthermore <p x and <p 2t are such that 
each switch in ti and f 2t+ i is linked to each v' as is required by the 
definition of a Benes" network. By our inductive hypothesis, v' is a 
Benes network. This is enough to prove that v is a Benes network. 

Let the notation [AftM\ denote a set of switches A e f , in the 
network <r. Similarly, let {J3/f i+1 (cr)} denote a set of switches B e f <+ , 
in <r. We define a relation R on the two sets A and 5 and write 

\A/UW)}B{Bn i+ M\ 

if every switch of A is linked to every switch of B in the network <r. 
For the cyclic Benes network v = Cm& * ' " w«C«+i > let tne switches 
in each stage be ordered. Note that the p< , for i = 1, 2, • • • t, in ? can 
be described by, 

|.T.(mod /.O/r.Wl^ln.^ - 1) + Z, : h = 1, 2, • • • n,/r« + iM) 



204 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971 

for 

x = 1,2, ■••/,• where /, = AT/n,n t+I , 
and 

<Pi = <P2t+i-i for i = t -\- 1, • • • 2t. 

Decompose the compex P = fa^fa '" <pit-\Z,it into {v\ , v 2 , ■■■ 
Vn j where v» , A = 1, 2, ■ • • ni , consists of those sets of switches: 

\h(modnd/t»(v)] 

\(h - i) fi«* + m *-™* = i. 2, • • • rK-/r*(v)| 

for fc = 3, 4, •■ • 2t - 1 

and 

{/i(modni)/f 2< (j')}. 

Then clearly v h e 5(n 2 , n 3 • • • n,+i), A = 1, 2, • • • n x . 

In each v h , let the switches in each stage be ordered as is consistent 
with their orderings in v. Suppose s, is a switch e f,(p A ) and g\ its co- 
ordinate in v h (i.e., s, is the grj tb switch in f,(v*))- Then s, e f,(i>) and 
has the coordinate g { in v. 

If we write g' { uniquely as 

g > = C n "i + <*« for C ^ 0, 1 ^ eft ^ ft »* (1) 

J -2 j-2 

(using the convention J]n f = 1 if i = 2 J 
then 0,- can be uniquely written as 

<7, = C ffn, + # + (h - 1) fin,- . (2) 



;=1 



Vice versa, if s, e £.•("), z ^ 1, 2f + 1, has coordinate #, as expressed 
in equation (2), then s, is also a switch in f <(»»») with coordinate <7< 
as expressed in equation (1). 

Next we show that v h is a cyclic Bene§ network, i.e., let v h = 
f^fa • • • <P2t-\$2t> then <p t , i = 2, 3 • • • t can be described by 

{s'(mod /O/tfMWn.Cr/ - 1) + h : Z, = 1, 2. • • • n,/rt + i(i*)} (3) 

for 

x' = \,2, ••• /< 



REARRANGEABLE NETWORKS 205 

where 

/' = N'/n t n t+1 and N' = N fn, , 

and 

<Pk = <P2i+i-k for k = t + 1, ■ • • 2t — 1. 

(Note that in equation (3), the two sets of switches are written in 
coordinates g' of v h .) From equations (1) and (2), 

i-i 
g . = mgl - (n, - m + (h - 1) II n, . (4) 

Let s, c f{("„) be a switch having coordinate g' t = x' (mod fj). Then 
we have the unique expression 

g '. = g ./j + x' for some g ^ 0. (5) 

Since HjlJ n, divides /J, from equations (1) and (5), there exists 
a unique u, g u ^ II)-i+i n i > such that 

x' = wlln, + ^. (6) 

»-2 

From equation (4), the corresponding g { is 

i-l 

g . = nMVi + *') - fa ~ Wi + (h-l)Jln i 

i-l 

= qnj'i + W - (n, - l)d{ + (h - 1) IK 

= qh + x (7) 

where /, = n x /J and 

i-l 

x = niX ' - ( ni - l)dj + (A - 1) II w, 

1-2 

= niu- n n,- + d{) - (n, - l)d{ + (h - 1) II n, , by (5) 

\ ,_2 / ' -2 

= ii-ii»i +« + (*- 1) n»* • (8) 



i-i 



It can be easily verified that ^ x < /, . 

Equation (7) says that a switch s< e f*(v») which has coordinate 
0< = z{ (mod /{) has coordinate g = x (mod /<) in v. 

Next we show that if the two sets {G' i+ i/ti+M} and {GWfr+iCO) 



206 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971 

are such that 

{.r'(mod /O/tfWMflWrt+ito) (9) 

and 

{z(mod WUtiWQi+itti+ify)} (10) 

hold, then G' i+J and G i+1 are coordinates of the same set of switches. 
Equation (9) implies 

(cwtf+ifa)} 

= Mx' - 1) + U : h , = 1, 2, • - . */#„&)!, 

- {»«(«• n »f + d' t - lj + Z,. : U - 1, 2, • • • n^tfrtk)} , 

- { w II ^ + (# - IK- + Z, : l { - 1, 2, .-. ni/tf+ifo)}- 
Equation (10) implies 

{GWft+ifr)) = {n { (x - 1) + l t : U = l, 2, • • • n,/r. +1 (^)}, 

- {»<(«■ n»* + « + Qt - 1) n^,- - 1) 



+ h:l<= l,2,..-n,/f,- +1 (,)|, 

{w Iln,- + (d'i - l)n t + (h - 1) fln y 

V j' = l ,_ 2 

+ Z« :Z, = 1,2, -•-m/ft+iO')}- 



- SW 



But from equation (2), if ^ = h ![*■.■»# + (<*J - IK + Z, , 1 g Z, ^ n if 
then its corresponding #-,- is 



i 



Q* = wll>/ + («*' - 1)»« + Z, + (A - 1) fin,- . 

Therefore [G' i+ i/?UM)} and [GWiWiMi are clearly coordinates 
of the same set of switches. 

That each switch in f x (i») is linked to each v' h by < Pl is a direct result of 

{z(mod 1^/tM\E[ni{x - 1) + h : h = 1, 2, • • ■ ih/r,(r)J 

since 



REARRANGEABLE NETWORKS 



207 



[h(mod U)\ n [ni(x - 1) + k : h - 1, 2, • • • %} | - 1 



for each A = 1, 2, • • • n x . 

Since v = faiti ■ ■ ' <p2«r 2 « +l is symmetric with respect to its middle 
stage, and v h z B(n 2 , n 3 , • • • n t + l ), clearly <p' k = <^ (+ i_* for fc = t + 1, 
• • • 2t — 1. And finally, again by an argument of symmetry, each 
switch in f 2 « + i is linked to each p' h by <p 2l . 



REFERENCES 



1. Benes, V. E., Mathematical Theory of Connecting Networks and Telephone 

Traffic, Chapter 3, New York: Academic Press, 1965. 

2. Hall, P., "On Representative of Subsets," J. London Math. Soc, 10 (1935), pp. 

26-30.